package william.array;

/**
 * @author ZhangShenao
 * @date 2024/3/3
 * @description <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/">...</a>
 */
public class Leetcode3_无重复字符的最长子串 {
    /**
     * 采用滑动窗口法
     * 在窗口[l,r]范围内,判断是否有重复字符
     * - 如果没有重复字符,则将r右移,扩充窗口
     * - 如果有重复字符,则将l右移,缩小窗口,直到将重复字符去除
     * 重复字符的判断,可以借助一个int[256]的frequency词频数组,记录每个字符出现的次数
     * <p>
     * 时间复杂度O(N) 只遍历数组一次
     * 空间复杂度O(1) 需要一个固定的int[256]空间大小
     */
    public int lengthOfLongestSubstring(String s) {
        //边界条件校验
        if (s == null || s.isEmpty()) {
            return 0;
        }

        //使用一个int[256]的frequency词频数组,用于校验重复字符
        int[] frequency = new int[256];

        //[l,r]为窗口大小
        int l = 0;
        int r = -1;

        int length = 0;
        int N = s.length();

        while (r < N - 1) {
            char c = s.charAt(r + 1);
            if (frequency[c] == 0) {   //字符不重复,扩充窗口
                frequency[c]++;
                r++;
            } else { //字符重复,缩小窗口
                frequency[s.charAt(l++)]--;
            }

            //更新最大长度
            length = Math.max(length, (r - l) + 1);
        }

        //返回最大长度
        return length;

    }
}
